#include "myTree.h"

using namespace std;


TreeNode::TreeNode(char d, TreeNode* left, TreeNode* right, NodeTag lt, NodeTag rt) {
    data = d;
    leftChild = left;
    rightChild = right;
    lTag = lt;
    rTag = rt;
}

TreeNode::TreeNode(char d) {
    data = d;
    leftChild = NULL;
    rightChild = NULL;
    lTag = Link;
    rTag = Link;
}

TreeNode::~TreeNode() {}

void TreeNode::printNode()
{
    cout << this->data;
}

MyTree::MyTree() {
    root = NULL;
    isThread = false;
}

TreeNode* MyTree::buildFromPreorder(const char arr[], int& index) {
    if (arr[index] == '@' || arr[index] == '\0') {
        index++;
        return NULL;
    }

    TreeNode* node = new TreeNode(arr[index++]);
    node->leftChild = buildFromPreorder(arr, index);
    node->rightChild = buildFromPreorder(arr, index);

    return node;
}

MyTree::MyTree(const char arr[]) {
    isThread = false;

    int index = 0;
    root = buildFromPreorder(arr, index);
}

TreeNode* MyTree::copyTree(TreeNode* node) {
    if (!node) {
        return NULL;
    }

    TreeNode* newNode = new TreeNode(node->data, nullptr, nullptr, node->lTag, node->rTag);

    if (node->lTag == Link) {
        newNode->leftChild = copyTree(node->leftChild);
    }

    if (node->rTag == Link) {
        newNode->rightChild = copyTree(node->rightChild);
    }

    return newNode;
}

MyTree::MyTree(const MyTree& other) {
    isThread = other.isThread;
    root = copyTree(other.root);
}

void MyTree::destroy(TreeNode* node) {
    if (node) {
        if (node->lTag == Link) {
            destroy(node->leftChild);
        }

        if (node->rTag == Link) {
            destroy(node->rightChild);
        }

        delete node;
    }
}

MyTree::~MyTree() {
    destroy(root);
}

void MyTree::preOrder(TreeNode* node) {
    if (node) {
        node->printNode();
        if (node->lTag == Link) {
            preOrder(node->leftChild);
        }

        if (node->rTag == Link) {
            preOrder(node->rightChild);
        }
    }
}

void MyTree::preOrderTraverse() {
    preOrder(root);
}

void MyTree::inOrder(TreeNode* node) {
    if (node) {
        if (node->lTag == Link) {
            inOrder(node->leftChild);
        }

        node->printNode();

        if (node->rTag == Link) {
            inOrder(node->rightChild);
        }
    }
}

void MyTree::inOrderTraverse() {
    if (isThread) {
        TreeNode* p = root;

        while (p && p->lTag == Link) {
            p = p->leftChild;
        }

        while (p) {
            p->printNode();
            p = &nextNode(*p);
        }
    }
    else {
        inOrder(root);
    }
}

void MyTree::postOrder(TreeNode* node) {
    if (node) {
        if (node->lTag == Link) {
            postOrder(node->leftChild);
        }

        if (node->rTag == Link) {
            postOrder(node->rightChild);
        }

        node->printNode();
    }
}

void MyTree::postOrderTraverse() {
    postOrder(root);
}

int MyTree::countLeaf(TreeNode* node) {
    if (!node) {
        return 0;
    }

    if (node->lTag == Link && !node->leftChild && node->rTag == Link && !node->rightChild) {
        return 1;
    }

    int leftCount = (node->lTag == Link) ? countLeaf(node->leftChild) : 0;

    int rightCount = (node->rTag == Link) ? countLeaf(node->rightChild) : 0;

    return leftCount + rightCount;
}

int MyTree::countLeaf() {
    return countLeaf(root);
}

int MyTree::countHeight(TreeNode* node) {
    if (!node) {
        return 0;
    }

    int leftHeight = (node->lTag == Link) ? countHeight(node->leftChild) : 0;

    int rightHeight = (node->rTag == Link) ? countHeight(node->rightChild) : 0;

    return max(leftHeight, rightHeight) + 1;
}

int MyTree::countHeight() {
    return countHeight(root);
}

bool MyTree::isThreadedTree() {
    return isThread;
}

void MyTree::inOrderThreading(TreeNode* node, TreeNode*& pre) {
    if (!node) {
        return;
    }

    inOrderThreading(node->leftChild, pre);

    if (!node->leftChild) {
        node->lTag = Thread;
        node->leftChild = pre;
    }

    if (pre && !pre->rightChild) {
        pre->rTag = Thread;
        pre->rightChild = node;
    }

    pre = node;

    inOrderThreading(node->rightChild, pre);
}

bool MyTree::inOrderThreading() {
    if (isThread) {
        return false;
    }
    
    TreeNode* pre = NULL;

    inOrderThreading(root, pre);

    if (pre) {
        pre->rTag = Thread;
        pre->rightChild = nullptr;
    }

    isThread = true;
    return true;
}

TreeNode* MyTree::locateNode(TreeNode* node, const char& v) {
    if (!node) {
        return NULL;
    }

    if (node->data == v) {
        return node;
    }

    TreeNode* leftResult = NULL;
    if (node->lTag == Link) {
        leftResult = locateNode(node->leftChild, v);
    }
        
    if (leftResult) {
        return leftResult;
    }

    TreeNode* rightResult = NULL;

    if (node->rTag == Link) {
        rightResult = locateNode(node->rightChild, v);
    }
        
    return rightResult;
}

TreeNode& MyTree::locateNode(const char& v) {
    TreeNode* result = locateNode(root, v);

    if (result) {
        return *result;
    }

    static TreeNode nullNode('@');

    return nullNode;
}

TreeNode& MyTree::preNode(const TreeNode& node) {
    if (node.lTag == Thread) {
        return *node.leftChild;
    }

    TreeNode* p = node.leftChild;

    if (p) {
        while (p->rTag == Link) {
            p = p->rightChild;
        }
    }
     
    if (p) {
        return *p;
    }

    static TreeNode dummy('\0');
    return dummy;
}

TreeNode& MyTree::nextNode(const TreeNode& node) {
    if (node.rTag == Thread) {
        return *node.rightChild;
    }

    TreeNode* p = node.rightChild;

    if (p) {
        while (p->lTag == Link) {
            p = p->leftChild;
        }
    }

    if (p) {
        return *p;
    }

    static TreeNode dummy('\0');
    return dummy;
}

HuffmanTree::HuffmanTree(const int& n, const int weights[]) {
    vector<HuffmanNode*> nodes;
    for (int i = 0; i < n; i++) {
        nodes.push_back(new HuffmanNode(weights[i]));
    }

    while (nodes.size() > 1) {
        for (int i = 0; i < nodes.size() - 1; i++) {
            for (int j = i + 1; j < nodes.size(); j++) {
                if (nodes[i]->weight > nodes[j]->weight) {
                    HuffmanNode* temp = nodes[i];
                    nodes[i] = nodes[j];
                    nodes[j] = temp;
                }
            }
        }

        HuffmanNode* left = nodes[0];
        HuffmanNode* right = nodes[1];
        HuffmanNode* parent = new HuffmanNode(left->weight + right->weight, left, right);

        nodes.erase(nodes.begin(), nodes.begin() + 2);
        nodes.push_back(parent);
    }

    root = nodes[0];
    generateCodes(root, "");

    for (int i = 0; i < codes.size() - 1; i++) {
        for (int j = i + 1; j < codes.size(); j++) {
            if (codes[i].first < codes[j].first) {
                pair<int, string> temp = codes[i];
                codes[i] = codes[j];
                codes[j] = temp;
            }
        }
    }
}

void HuffmanTree::destroy(HuffmanNode* node) {
    if (node) {
        destroy(node->left);
        destroy(node->right);
        delete node;
    }
}

HuffmanTree::~HuffmanTree() {
    destroy(root);
}

void HuffmanTree::generateCodes(HuffmanNode* node, string code) {
    if (!node) {
        return;
    }

    if (!node->left && !node->right) {
        codes.push_back(make_pair(node->weight, code));
        return;
    }

    if (node->left) {
        generateCodes(node->left, code + "0");
    }

    if (node->right) {
        generateCodes(node->right, code + "1");
    }
}

bool HuffmanTree::compare(const HuffmanNode* a, const HuffmanNode* b) {
    return a->weight < b->weight;
}

void HuffmanTree::printHuffmanCodes() {
    for (const auto& pair : codes) {
        cout << pair.first << ":" << pair.second << endl;
    }
}